From 5f13305fc469b645d1f0eb2abc12d7c6ec0f238a Mon Sep 17 00:00:00 2001 From: "awilliam@xenbuild.aw" Date: Sat, 14 Oct 2006 16:42:15 -0600 Subject: [PATCH] [IA64] linux/include/linux/hash.h. Signed-off-by: Isaku Yamahata --- xen/include/asm-ia64/linux/README.origin | 1 + xen/include/asm-ia64/linux/hash.h | 58 ++++++++++++++++++++++++ 2 files changed, 59 insertions(+) create mode 100644 xen/include/asm-ia64/linux/hash.h diff --git a/xen/include/asm-ia64/linux/README.origin b/xen/include/asm-ia64/linux/README.origin index cb7c02b0a2..e364b52977 100644 --- a/xen/include/asm-ia64/linux/README.origin +++ b/xen/include/asm-ia64/linux/README.origin @@ -7,6 +7,7 @@ bcd.h -> linux/include/linux/bcd.h bitmap.h -> linux/include/linux/bitmap.h bitops.h -> linux/include/linux/bitops.h +hash.h -> linux/include/linux/hash.h initrd.h -> linux/include/linux/initrd.h jiffies.h -> linux/include/linux/jiffies.h kmalloc_sizes.h -> linux/include/linux/kmalloc_sizes.h diff --git a/xen/include/asm-ia64/linux/hash.h b/xen/include/asm-ia64/linux/hash.h new file mode 100644 index 0000000000..acf17bb8e7 --- /dev/null +++ b/xen/include/asm-ia64/linux/hash.h @@ -0,0 +1,58 @@ +#ifndef _LINUX_HASH_H +#define _LINUX_HASH_H +/* Fast hashing routine for a long. + (C) 2002 William Lee Irwin III, IBM */ + +/* + * Knuth recommends primes in approximately golden ratio to the maximum + * integer representable by a machine word for multiplicative hashing. + * Chuck Lever verified the effectiveness of this technique: + * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf + * + * These primes are chosen to be bit-sparse, that is operations on + * them can use shifts and additions instead of multiplications for + * machines where multiplications are slow. + */ +#if BITS_PER_LONG == 32 +/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ +#define GOLDEN_RATIO_PRIME 0x9e370001UL +#elif BITS_PER_LONG == 64 +/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ +#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL +#else +#error Define GOLDEN_RATIO_PRIME for your wordsize. +#endif + +static inline unsigned long hash_long(unsigned long val, unsigned int bits) +{ + unsigned long hash = val; + +#if BITS_PER_LONG == 64 + /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ + unsigned long n = hash; + n <<= 18; + hash -= n; + n <<= 33; + hash -= n; + n <<= 3; + hash += n; + n <<= 3; + hash -= n; + n <<= 4; + hash += n; + n <<= 2; + hash += n; +#else + /* On some cpus multiply is faster, on others gcc will do shifts */ + hash *= GOLDEN_RATIO_PRIME; +#endif + + /* High bits are more random, so use them. */ + return hash >> (BITS_PER_LONG - bits); +} + +static inline unsigned long hash_ptr(void *ptr, unsigned int bits) +{ + return hash_long((unsigned long)ptr, bits); +} +#endif /* _LINUX_HASH_H */ -- 2.30.2